{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Vowels Permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countVowelPermutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计元音字母序列的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>，请你帮忙统计一下我们可以按下述规则形成多少个长度为&nbsp;<code>n</code>&nbsp;的字符串：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>字符串中的每个字符都应当是小写元音字母（<code>&#39;a&#39;</code>, <code>&#39;e&#39;</code>, <code>&#39;i&#39;</code>, <code>&#39;o&#39;</code>, <code>&#39;u&#39;</code>）</li>\n",
    "\t<li>每个元音&nbsp;<code>&#39;a&#39;</code>&nbsp;后面都只能跟着&nbsp;<code>&#39;e&#39;</code></li>\n",
    "\t<li>每个元音&nbsp;<code>&#39;e&#39;</code>&nbsp;后面只能跟着&nbsp;<code>&#39;a&#39;</code>&nbsp;或者是&nbsp;<code>&#39;i&#39;</code></li>\n",
    "\t<li>每个元音&nbsp;<code>&#39;i&#39;</code>&nbsp;后面&nbsp;<strong>不能</strong> 再跟着另一个&nbsp;<code>&#39;i&#39;</code></li>\n",
    "\t<li>每个元音&nbsp;<code>&#39;o&#39;</code>&nbsp;后面只能跟着&nbsp;<code>&#39;i&#39;</code>&nbsp;或者是&nbsp;<code>&#39;u&#39;</code></li>\n",
    "\t<li>每个元音&nbsp;<code>&#39;u&#39;</code>&nbsp;后面只能跟着&nbsp;<code>&#39;a&#39;</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>由于答案可能会很大，所以请你返回 模&nbsp;<code>10^9 + 7</code>&nbsp;之后的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>所有可能的字符串分别是：&quot;a&quot;, &quot;e&quot;, &quot;i&quot; , &quot;o&quot; 和 &quot;u&quot;。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>所有可能的字符串分别是：&quot;ae&quot;, &quot;ea&quot;, &quot;ei&quot;, &quot;ia&quot;, &quot;ie&quot;, &quot;io&quot;, &quot;iu&quot;, &quot;oi&quot;, &quot;ou&quot; 和 &quot;ua&quot;。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 5\n",
    "<strong>输出：</strong>68</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2 * 10^4</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-vowels-permutation](https://leetcode.cn/problems/count-vowels-permutation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-vowels-permutation](https://leetcode.cn/problems/count-vowels-permutation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def recur(end, remain):\n",
    "            if remain == 0:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            if end == 'a':\n",
    "                ans = recur('e', remain - 1)\n",
    "            elif end == 'e':\n",
    "                ans = recur('a', remain -1) + recur('i', remain - 1)\n",
    "            elif end == 'i':\n",
    "                ans = recur('a', remain -1) + recur('e', remain - 1) + recur('o', remain - 1) + recur('u', remain - 1)\n",
    "            elif end == 'o':\n",
    "                ans = recur('i', remain -1) + recur('u', remain - 1)\n",
    "            else:\n",
    "                ans = recur('a', remain -1)\n",
    "            return ans % MOD\n",
    "        ans = 0\n",
    "        for e in ['a', 'e', 'i', 'o', 'u']:\n",
    "            ans += recur(e, n - 1)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        dp = [1]*5\n",
    "        for _ in range(n-1):\n",
    "            dp[0],dp[1],dp[2],dp[3],dp[4] = dp[2]+dp[1]+dp[4],\\\n",
    "            dp[0]+dp[2],dp[1]+dp[3],dp[2],dp[2]+dp[3]\n",
    "        return sum(dp)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        yuan=[1,1,1,1,1]\n",
    "        if n==1:\n",
    "            return 5\n",
    "        else:\n",
    "            for i in range(1,n):\n",
    "                syuan=yuan.copy()\n",
    "                yuan[0]=(syuan[1]+syuan[2]+syuan[4])%(10**9+7)\n",
    "                yuan[1]=(syuan[0]+syuan[2])%(10**9+7)\n",
    "                yuan[2]=(syuan[1]+syuan[3])%(10**9+7)\n",
    "                yuan[3]=syuan[2]%(10**9+7)\n",
    "                yuan[4]=(syuan[2]+syuan[3])%(10**9+7)\n",
    "            return sum(yuan) %(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        dp = (1, 1, 1, 1, 1)\n",
    "        for _ in range(n - 1):\n",
    "            dp = ((dp[1] + dp[2] + dp[4]) % 1000000007, (dp[0] + dp[2]) % 1000000007, (dp[1] + dp[3]) % 1000000007, dp[2], (dp[2] + dp[3]) % 1000000007)\n",
    "        return sum(dp) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "\n",
    "        MOD = (10 ** 9 + 7)\n",
    "\n",
    "        # Solution: Dynamic Programming\n",
    "\n",
    "        dp = [1] * 5\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            new_dp = []\n",
    "            new_dp.append(dp[1] % MOD)\n",
    "            new_dp.append((dp[0] + dp[2]) % MOD)\n",
    "            new_dp.append((dp[0] + dp[1] + dp[3] + dp[4]) % MOD)\n",
    "            new_dp.append((dp[2] + dp[4]) % MOD)\n",
    "            new_dp.append(dp[0] % MOD)\n",
    "            dp = new_dp\n",
    "        \n",
    "        return sum(dp) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        dp = [[0] * 5 for _ in range(n)]\n",
    "        for i in range(5):\n",
    "            dp[0][i] = 1\n",
    "        modNum = pow(10, 9) + 7\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][1]\n",
    "            dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % modNum\n",
    "            dp[i][2] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][3] + dp[i-1][4]) % modNum\n",
    "            dp[i][3] = (dp[i-1][2] + dp[i-1][4]) % modNum\n",
    "            dp[i][4] = dp[i-1][0]\n",
    "        res = 0\n",
    "        for i in range(5):\n",
    "            res += dp[n-1][i]\n",
    "            res = res % modNum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9) + 7\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        f = [[1] * 5] + [[0] * 5 for _ in range(n - 1)]\n",
    "        for i in range(1, n):\n",
    "            f[i][0] = f[i-1][1]\n",
    "            f[i][1] = (f[i-1][0] + f[i-1][2]) % MOD\n",
    "            f[i][2] = ((((f[i-1][0] + f[i-1][1]) % MOD + f[i-1][3]) % MOD) + f[i-1][4]) % MOD\n",
    "            f[i][3] = (f[i-1][2] + f[i-1][4]) % MOD\n",
    "            f[i][4] = f[i-1][0]\n",
    "        return (((((f[-1][0] + f[-1][1]) % MOD + f[-1][2]) % MOD + f[-1][3]) % MOD) + f[-1][4]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        dp=[[0 for _ in range(5)]for _ in range(n)]\n",
    "        for i in range(5):\n",
    "            dp[0][i]=1\n",
    "        mod=10**9+7\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=dp[i-1][1]%mod\n",
    "            dp[i][1]=(dp[i-1][0]+dp[i-1][2])%mod\n",
    "            dp[i][2]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][3]+dp[i-1][4])%mod\n",
    "            dp[i][3]=(dp[i-1][2]+dp[i-1][4])%mod\n",
    "            dp[i][4]=(dp[i-1][0])%mod\n",
    "        return sum(dp[-1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "\n",
    "        legal_nxt = {\n",
    "            'a':['e'],\n",
    "            'e':['a', 'i'],\n",
    "            'i':['a', 'e', 'o', 'u'],\n",
    "            'o':['i', 'u'],\n",
    "            'u':['a']\n",
    "        }\n",
    "\n",
    "        \"\"\"\n",
    "        @cache\n",
    "        def dfs(i, ch):\n",
    "            if i == n - 1:\n",
    "                return 1\n",
    "            \n",
    "            ret = 0\n",
    "            for nxt_ch in legal_nxt[ch]:\n",
    "                ret = (ret + dfs(i + 1, nxt_ch)) % int(1e9 + 7)\n",
    "            return ret\n",
    "\n",
    "        ans = 0\n",
    "        for ch in ['a', 'e', 'i', 'o', 'u']:\n",
    "            ans = (ans + dfs(0, ch)) % int(1e9 + 7)\n",
    "        \"\"\"\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "        # 最后1个字母可以是任意一个\n",
    "        dp[-1] = {ch:1 for ch in ['a', 'e', 'i', 'o', 'u']}\n",
    "        mod = int(1e9 + 7)\n",
    "        \n",
    "        # 这里需要逆向遍历，因为我们只知道下一个字符的合法值，否则需要把规则逆向。\n",
    "        for i in reversed(range(n - 1)):\n",
    "            for cur_ch in ['a', 'e', 'i', 'o', 'u']:\n",
    "                for nxt_ch in legal_nxt[cur_ch]:\n",
    "                    dp[i][cur_ch] = (dp[i][cur_ch] + dp[i + 1][nxt_ch]) % mod\n",
    "\n",
    "        ans = 0\n",
    "        for ch, v in dp[0].items():\n",
    "            ans = (ans + v) % mod\n",
    "\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        m = 10**9+7\n",
    "        ref = [[[]for i in range(5)]for i in range(n)]\n",
    "        for i in range(5):\n",
    "            ref[0][i] = 1\n",
    "        for i in range(1,n):\n",
    "            ref[i][0] = (ref[i-1][1]+ref[i-1][2]+ref[i-1][4])%m\n",
    "            ref[i][1] = (ref[i-1][0]+ref[i-1][2])%m\n",
    "            ref[i][2] = (ref[i-1][1]+ref[i-1][3])%m\n",
    "            ref[i][3] = ref[i-1][2]\n",
    "            ref[i][4] = (ref[i-1][3]+ref[i-1][2])%m\n",
    "        res = 0\n",
    "        for j in range(5):\n",
    "            res += ref[n-1][j]\n",
    "        #print (ref)\n",
    "        return res%m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        dp = [[[0, 0] for _ in range(5)] for _ in range(n)]\n",
    "        dp[0] = [[1, 1], [1, 1], [1, 1], [1, 1], [1, 1]]\n",
    "        d = [[1], [0,2], [0,1,3,4], [2,4], [0]]\n",
    "        for i in range(1, n):\n",
    "            for j in range(5):\n",
    "                status, c = dp[i-1][j]\n",
    "                if status:  # dp[i-1]中 序号为j的字符出现过\n",
    "                    for k in d[j]:\n",
    "                        dp[i][k][0] = 1\n",
    "                        dp[i][k][1] = (dp[i][k][1] + c) % MOD\n",
    "\n",
    "        return sum([v[1] for v in dp[n-1]]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution(object):\n",
    "\n",
    "    def countVowelPermutation(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums=np.array( [ [0,1,0,0,0],[1,0,1,0,0],[1,1,0,1,1],[0,0,1,0,1],[1,0,0,0,0] ] )\n",
    "        result=np.ones((1,5))\n",
    "        for i in range(1,n):\n",
    "            result=np.dot(result,nums) %(1000000000+ 7)\n",
    "        return int(result.sum() %(1000000000+ 7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    ans_a = {}\n",
    "    ans_e = {}\n",
    "    ans_i = {}\n",
    "    ans_o = {}\n",
    "    ans_u = {}\n",
    "\n",
    "    def startWithAlpha(self, alp, cnt):\n",
    "        ret = eval('self.ans_'+alp).get(cnt, 0)\n",
    "        if ret != 0:\n",
    "            return ret\n",
    "        if cnt == 0:\n",
    "            ret = 1\n",
    "        elif alp == 'a':\n",
    "            ret = self.startWithAlpha('e', cnt-1)\n",
    "        elif alp == 'e':\n",
    "            ret = self.startWithAlpha('a', cnt-1) + self.startWithAlpha('i', cnt-1)\n",
    "        elif alp == 'i':\n",
    "            ret = self.startWithAlpha('a', cnt-1) + self.startWithAlpha('e', cnt-1) + self.startWithAlpha('o', cnt-1) + self.startWithAlpha('u', cnt-1)\n",
    "        elif alp == 'o':\n",
    "            ret = self.startWithAlpha('u', cnt-1) + self.startWithAlpha('i', cnt-1)\n",
    "        elif alp == 'u':\n",
    "            ret = self.startWithAlpha('a', cnt-1)\n",
    "        ret = int(ret%(1e9 + 7))\n",
    "        eval('self.ans_'+alp)[cnt] = ret\n",
    "        return ret\n",
    "\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        ret = 0\n",
    "        for st in ('a', 'e', 'i', 'o', 'u'):\n",
    "            ret += self.startWithAlpha(st, n-1)\n",
    "        return int(ret%(1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "MOD = 10 ** 9 + 7\n",
    "dtype = np.dtype('uint64')\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        ans, mat = np.ones(5, dtype=dtype), np.array([[0, 1, 1, 0, 1], [1, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 0, 1, 0, 0], [0, 0, 1, 1, 0]],dtype=dtype)\n",
    "        n -= 1\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                ans = mat @ ans % MOD\n",
    "            mat = mat @ mat % MOD\n",
    "            n >>= 1\n",
    "        return int(ans.sum()) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        #dp[(i,c)] = num of str of len=i\n",
    "        #where last char is c, \n",
    "        #map each vowel to a index\n",
    "        a,e,i,o, u=0,1,2,3,4\n",
    "        dp = {(1,c): 1 for c in range(5)}\n",
    "        \n",
    "        mod = 10**9 + 7\n",
    "        for j in range(2, n+ 1):\n",
    "            dp[(j, a)] = (dp[(j - 1, e)] + dp[(j - 1, i)] + dp[(j - 1, u)])%mod\n",
    "            dp[(j, e)] = (dp[(j - 1, a)] + dp[(j - 1, i)])%mod\n",
    "            dp[(j, i)] = (dp[(j - 1, e)] + dp[(j - 1, o)])%mod\n",
    "            dp[(j, o)] = (dp[(j - 1, i)])%mod\n",
    "            dp[(j, u)] = (dp[(j - 1, i)] + dp[(j - 1, o)])%mod\n",
    "        res = 0\n",
    "        for i in range(5):\n",
    "            res += dp[(n, i)]\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "chars = ['a', 'e', 'i', 'o', 'u']\n",
    "char_map = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}\n",
    "char_next_map = {'a': ['e'], 'e': ['a', 'i'], 'i': ['a', 'e', 'o', 'u'], 'o': ['i', 'u'], 'u': ['a']}\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        self.dp = [[-1] * 5 for _ in range(n)]\n",
    "        for c in chars:\n",
    "            self.dfs(0, n, c)\n",
    "        return sum(self.dp[0]) % 1000000007\n",
    "    def dfs(self, i: int, n: int, curr: str) -> int:\n",
    "        if i == n - 1:\n",
    "            self.dp[i][char_map.get(curr)] = 1\n",
    "            return 1\n",
    "        if self.dp[i][char_map.get(curr)] >= 0:\n",
    "            return self.dp[i][char_map.get(curr)]\n",
    "        res = 0\n",
    "        for next in char_next_map[curr]:\n",
    "            res += self.dfs(i + 1, n, next)\n",
    "            res %= 1000000007\n",
    "        self.dp[i][char_map.get(curr)] = res\n",
    "        #print(i, curr, char_map.get(curr), self.dp[i][char_map.get(curr)])\n",
    "        return res % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        def countVowelPermutation_sub(num):\n",
    "            if num==1:\n",
    "                return 1,1,1,1,1\n",
    "            else:\n",
    "                a,e,i,o,u=countVowelPermutation_sub(num-1)\n",
    "                return e+i+u, a+i, e+o, i, i+o\n",
    "        a,e,i,o,u=countVowelPermutation_sub(n)\n",
    "        return (a+e+i+o+u)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "@cache\n",
    "def f(n, x):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    if x == 'a':\n",
    "        return f(n-1, 'e')\n",
    "    if x == 'u':\n",
    "        return f(n-1, 'a')\n",
    "    if x == 'e':\n",
    "        return (f(n-1, 'a') + f(n-1, 'i')) % MOD\n",
    "    if x == 'o':\n",
    "        return (f(n-1, 'u') + f(n-1, 'i')) % MOD\n",
    "    if x == 'i':\n",
    "        return (f(n-1, 'a') + f(n-1, 'e') + f(n-1, 'o') + f(n-1, 'u')) % MOD\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        '''\n",
    "        给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：\n",
    "\n",
    "        字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）\n",
    "        每个元音 'a' 后面都只能跟着 'e'\n",
    "        每个元音 'e' 后面只能跟着 'a' 或者是 'i'\n",
    "        每个元音 'i' 后面 不能 再跟着另一个 'i'\n",
    "        每个元音 'o' 后面只能跟着 'i' 或者是 'u'\n",
    "        每个元音 'u' 后面只能跟着 'a'\n",
    "        由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。\n",
    "        '''\n",
    "\n",
    "        \n",
    "        ans = 0\n",
    "        for x in \"aeiou\":\n",
    "            ans += f(n, x)\n",
    "            ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        f = [[-1] * 5 for _ in range(n + 5)]\n",
    "        def dfs(i, c) -> int:\n",
    "            if i >= n:\n",
    "                return 1\n",
    "            if f[i][c] != -1:\n",
    "                return f[i][c]\n",
    "            if c == 0:\n",
    "                f[i][c] = dfs(i + 1, 1) % MOD\n",
    "            elif c == 1:\n",
    "                f[i][c] = dfs(i + 1, 0) + dfs(i + 1, 2) % MOD\n",
    "            elif c == 2:\n",
    "                f[i][c] = sum(dfs(i + 1, c) for c in [0,1,3,4]) % MOD\n",
    "            elif c == 3:\n",
    "                f[i][c] = dfs(i + 1, 2) + dfs(i + 1, 4) % MOD\n",
    "            else:\n",
    "                f[i][c] = dfs(i + 1, 0) % MOD\n",
    "            return f[i][c]\n",
    "        return sum(dfs(1, c) for c in range(5)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        @lru_cache()\n",
    "        def a(n):\n",
    "            return e(n - 1) % mod if n != 1 else 1\n",
    "        @lru_cache()\n",
    "        def e(n):\n",
    "            return (a(n - 1) + i(n - 1)) % mod if n != 1 else 1\n",
    "        @lru_cache()\n",
    "        def i(n):\n",
    "            return (a(n - 1) + e(n - 1) + o(n - 1) + u(n - 1)) % mod if n != 1 else 1\n",
    "        @lru_cache()\n",
    "        def o(n):\n",
    "            return (i(n - 1) + u(n - 1)) % mod if n != 1 else 1\n",
    "        @lru_cache()\n",
    "        def u(n):\n",
    "            return a(n - 1) % mod if n != 1 else 1\n",
    "        return (a(n) + e(n) + i(n) + o(n) + u(n)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "MAX = int(1e9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        cache:List[List[int]] = [[-1 for i in range(6)] for i in range(n)]\n",
    "        # c 1-5表示aeiou 0表示开头\n",
    "        def dfs(i:int, c:int) -> int:\n",
    "            if i == n:\n",
    "                return 1\n",
    "            if (v := cache[i][c]) != -1:\n",
    "                return v\n",
    "\n",
    "            cnt = 0\n",
    "            if c == 0:\n",
    "                for j in range(5):\n",
    "                    cnt += dfs(i + 1, j + 1)\n",
    "            else:\n",
    "                if c == 1:\n",
    "                    cnt += dfs(i + 1, 2)\n",
    "                elif c == 2:\n",
    "                    cnt += dfs(i + 1, 1)\n",
    "                    cnt += dfs(i + 1, 3)\n",
    "                elif c == 3:\n",
    "                    cnt += dfs(i + 1, 1)\n",
    "                    cnt += dfs(i + 1, 2)\n",
    "                    cnt += dfs(i + 1, 4)\n",
    "                    cnt += dfs(i + 1, 5)\n",
    "                elif c == 4:\n",
    "                    cnt += dfs(i + 1, 3)\n",
    "                    cnt += dfs(i + 1, 5)\n",
    "                else:\n",
    "                    cnt += dfs(i + 1, 1)\n",
    "            cnt %= MAX\n",
    "            cache[i][c] = cnt\n",
    "            return cnt\n",
    "\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "\n",
    "@cache\n",
    "def f(last, k):\n",
    "    if k == 1:\n",
    "        if last == '':\n",
    "            return 5\n",
    "        if last in 'au':\n",
    "            return 1\n",
    "        if last in 'eo':\n",
    "            return 2\n",
    "        if last in 'i':\n",
    "            return 4\n",
    "    if last == '':\n",
    "        return sum(f(c, k-1) for c in 'aeiou') % MOD\n",
    "    if last == 'a':\n",
    "        return sum(f(c, k-1) for c in 'e') % MOD\n",
    "    if last == 'e':\n",
    "        return sum(f(c, k-1) for c in 'ai') % MOD\n",
    "    if last == 'i':\n",
    "        return sum(f(c, k-1) for c in 'aeou') % MOD\n",
    "    if last == 'o':\n",
    "        return sum(f(c, k-1) for c in 'iu') % MOD \n",
    "    if last == 'u':\n",
    "        return sum(f(c, k-1) for c in 'a') % MOD\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:   \n",
    "        return f('', n) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        @lru_cache()\n",
    "        def counting(n):\n",
    "            if n == 1:\n",
    "                return [1, 1, 1, 1, 1]\n",
    "            else:\n",
    "                x = counting(n - 1)\n",
    "                return [\n",
    "                    x[1]+x[2]+x[4],\n",
    "                    x[0]+x[2],\n",
    "                    x[1]+x[3],\n",
    "                    x[2],\n",
    "                    x[2]+x[3]\n",
    "                ]\n",
    "        return sum(counting(n)) % (1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        ck={}\n",
    "        ck['']=['a','e','i','o','u']\n",
    "        ck['a']=['e']\n",
    "        ck['e']=['a','i']\n",
    "        ck['i']=['a','e','o','u']\n",
    "        ck['o']=['i','u']\n",
    "        ck['u']=['a']\n",
    "\n",
    "        @cache\n",
    "        def dp(i,x):\n",
    "            if i==n:\n",
    "                return 1\n",
    "            res=0\n",
    "            for y in ck[x]:\n",
    "                res+=dp(i+1,y)\n",
    "                res%=(10**9+7)\n",
    "            return res\n",
    "\n",
    "        return dp(0,'')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, c) -> int:\n",
    "            if i >= n:\n",
    "                return 1 \n",
    "            if c == 'a':\n",
    "                return dfs(i + 1, 'e') % MOD\n",
    "            elif c == 'e':\n",
    "                return dfs(i + 1, 'a') + dfs(i + 1, 'i') % MOD\n",
    "            elif c == 'i':\n",
    "                return sum(dfs(i + 1, c) for c in \"aeou\") % MOD\n",
    "            elif c == 'o':\n",
    "                return dfs(i + 1, 'i') + dfs(i + 1, 'u') % MOD\n",
    "            else:\n",
    "                return dfs(i + 1, 'a') % MOD\n",
    "        return sum(dfs(1, c) for c in \"aeiou\") % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        ret = [([-1] * n) for x in range(5)]\n",
    "        m = 1000000007\n",
    "        def get_ret(cur, n):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            if ret[cur][n - 1] >= 0:\n",
    "                return ret[cur][n - 1]\n",
    "            r = 0\n",
    "            if cur == 0:\n",
    "                r = get_ret(1, n - 1)\n",
    "            elif cur == 1:\n",
    "                r = get_ret(0, n - 1) + get_ret(2, n - 1)\n",
    "            elif cur == 2:\n",
    "                r = get_ret(0, n - 1) + get_ret(1, n - 1) + get_ret(3, n - 1) + get_ret(4, n - 1)\n",
    "            elif cur == 3:\n",
    "                r = get_ret(2, n - 1) + get_ret(4, n - 1)\n",
    "            else:\n",
    "                r = get_ret(0, n - 1)\n",
    "            r %= m\n",
    "            ret[cur][n - 1] = r\n",
    "            return r\n",
    "        return (get_ret(0, n - 1) + get_ret(1, n - 1) + get_ret(2, n - 1) + get_ret(3, n - 1) + get_ret(4, n - 1)) % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        Mod = 10**9+7\n",
    "        dic = {'a':['e'],'e':['a','i'],'i':['a','e','o','u'],'o':['i','u'],'u':['a']}\n",
    "        @cache\n",
    "        def dfs(i,res):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            for x in res:\n",
    "                cnt += dfs(i+1,tuple(dic[x])) % Mod\n",
    "            return cnt % Mod\n",
    "\n",
    "        return dfs(0,('a','e','i','o','u'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[0,0,0,0,0] for i in range(n)]\n",
    "        for j in range(5): dp[0][j] = 1\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][1] + dp[i-1][2] + dp[i-1][4] % MOD\n",
    "            dp[i][1] = dp[i-1][0] + dp[i-1][2] % MOD\n",
    "            dp[i][2] = dp[i-1][1] + dp[i-1][3] % MOD\n",
    "            dp[i][3] = dp[i-1][2] % MOD\n",
    "            dp[i][4] = dp[i-1][2] + dp[i-1][3] % MOD\n",
    "        return sum(dp[n-1]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "\n",
    "        \"\"\"\n",
    "        a: e\n",
    "        e: a i\n",
    "        i: a e o u\n",
    "        o: i u\n",
    "        u: a\n",
    "        \"\"\"\n",
    "        graph = {\"a\":[\"e\"], \"e\":[\"a\", \"i\"], \"i\":[\"a\", \"e\", \"o\", \"u\"], \"o\":[\"i\", \"u\"], \"u\":[\"a\"]}\n",
    "        \n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(c, n):\n",
    "            # 以c为开头 长为n的总数\n",
    "            if n == 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for x in graph[c]:\n",
    "                res += dfs(x, n-1)\n",
    "                res %= MOD\n",
    "            return res\n",
    "        res = 0\n",
    "        for x in graph:\n",
    "            res += dfs(x, n)\n",
    "            res %= MOD \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        mod = 10 **9+7\n",
    "        @lru_cache(None)\n",
    "        def dp(n,c):\n",
    "            if n==1:\n",
    "                return 1\n",
    "            if c=='a':\n",
    "                return dp(n-1,'e') %mod\n",
    "            elif c=='e':\n",
    "                return sum(dp(n-1,k) for k in 'ai')%mod\n",
    "            elif c=='i':\n",
    "                return sum(dp(n-1,k) for k in 'aeou')%mod\n",
    "            elif c=='o':\n",
    "                return sum(dp(n-1,k) for k in 'iu')%mod\n",
    "            elif c=='u':\n",
    "                return dp(n-1,'a') %mod\n",
    "        return sum(dp(n,k) for k in 'aeoiu') %mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        \n",
    "        @cache\n",
    "        def f(last, k):\n",
    "            if k == 1:\n",
    "                if last == '':\n",
    "                    return 5\n",
    "                if last in 'au':\n",
    "                    return 1\n",
    "                if last in 'eo':\n",
    "                    return 2\n",
    "                if last in 'i':\n",
    "                    return 4\n",
    "            if last == '':\n",
    "                return sum(f(c, k-1) for c in 'aeiou') % MOD\n",
    "            if last == 'a':\n",
    "                return sum(f(c, k-1) for c in 'e') % MOD\n",
    "            if last == 'e':\n",
    "                return sum(f(c, k-1) for c in 'ai') % MOD\n",
    "            if last == 'i':\n",
    "                return sum(f(c, k-1) for c in 'aeou') % MOD\n",
    "            if last == 'o':\n",
    "                return sum(f(c, k-1) for c in 'iu') % MOD \n",
    "            if last == 'u':\n",
    "                return sum(f(c, k-1) for c in 'a') % MOD\n",
    "\n",
    "            \n",
    "        return f('', n) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, last_char):\n",
    "            if idx == n:\n",
    "                return 1\n",
    "            return sum(dfs(idx + 1, char) for char in vowels[last_char]) % MOD\n",
    "\n",
    "        vowels = {'a': ['e'], 'e': ['a', 'i'], 'i': ['a', 'e', 'o', 'u'], 'o': ['i', 'u'], 'u': ['a']}\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return sum(dfs(1, char) for char in vowels) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        nxt, MOD = [[1], [0, 2], [0, 1, 3, 4], [2, 4], [0]], 1000000007\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, i):\n",
    "            if i == n - 1: return 1\n",
    "            return sum([dfs(idx_nxt, i + 1) for idx_nxt in nxt[idx]]) % MOD\n",
    "\n",
    "        return sum([dfs(idx, 0) for idx in range(5)]) % MOD\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        from functools import lru_cache\n",
    "        import sys; sys.setrecursionlimit(200000000)\n",
    "        \n",
    "        def _mod(fn):\n",
    "            def _(*args, **kwargs):\n",
    "                return fn(*args, **kwargs)%(1000000007)\n",
    "            return _\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        @_mod\n",
    "        def f(n, c=None):\n",
    "            if c == None:\n",
    "                return f(n, 'a') + f(n, 'e') + f(n, 'i') + f(n, 'o') + f(n, 'u')\n",
    "            elif n <= 1:\n",
    "                return 1 if n == 1 else 0\n",
    "            else:\n",
    "                if c == 'a':\n",
    "                    return f(n-1, 'u') + f(n-1, 'e') + f(n-1, 'i')\n",
    "                elif c == 'e':\n",
    "                    return f(n-1, 'a') + f(n-1, 'i')\n",
    "                elif c == 'i':\n",
    "                    return f(n-1, 'o') + f(n-1, 'e')\n",
    "                elif c == 'o':\n",
    "                    return f(n-1, 'i')\n",
    "                elif c == 'u':\n",
    "                    return f(n-1, 'o') + f(n-1, 'i')\n",
    "                else:\n",
    "                    return None\n",
    "        return f(n) % (1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        a = [0] * n\n",
    "        e = [0] * n\n",
    "        i = [0] * n\n",
    "        o = [0] * n\n",
    "        u = [0] * n\n",
    "        a[0], e[0], i[0], o[0], u[0] = 1,1,1,1,1\n",
    "        for j in range(1, n):\n",
    "            a[j] = e[j-1]\n",
    "            e[j] = a[j-1] + i[j-1]\n",
    "            i[j] = a[j-1] + e[j-1] + o[j-1] + u[j-1]\n",
    "            o[j] = i[j-1] + u[j-1]\n",
    "            u[j] = a[j-1]\n",
    "        return (a[-1] + e[-1] + i[-1] + o[-1] + u[-1]) % MOD\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# 字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）\n",
    "# 每个元音'a'后面都只能跟着'e'\n",
    "# 每个元音'e'后面只能跟着'a'或者是'i'\n",
    "# 每个元音'i'后面不能 再跟着另一个'i'\n",
    "# 每个元音'o'后面只能跟着'i'或者是'u'\n",
    "# 每个元音'u'后面只能跟着'a'\n",
    "#\n",
    "# 来源：力扣（LeetCode）\n",
    "# 链接：https://leetcode-cn.com/problems/count-vowels-permutation\n",
    "# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        alphabet=[\"a\",\"e\",\"i\",\"o\",\"u\"]\n",
    "        resultlist=[[1] for i in range(5)]\n",
    "        for i in range(n-1):\n",
    "            resultlist[0].append(resultlist[1][i])\n",
    "            resultlist[1].append(resultlist[0][i]+resultlist[2][i])\n",
    "            resultlist[2].append(resultlist[0][i]+resultlist[1][i]+resultlist[3][i]+resultlist[4][i])\n",
    "            resultlist[3].append(resultlist[2][i]+resultlist[4][i])\n",
    "            resultlist[4].append(resultlist[0][i])\n",
    "        return (resultlist[0][-1]+resultlist[1][-1]+resultlist[2][-1]+resultlist[3][-1]+resultlist[4][-1])%(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        dp = [[1 for _ in range(n+1)] for _ in range(5)]\n",
    "        for j in range(2, n+1):\n",
    "            dp[0][j] = dp[1][j-1]\n",
    "            dp[1][j] = dp[0][j-1] + dp[2][j-1]\n",
    "            dp[2][j] = dp[0][j-1] + dp[1][j-1] + dp[3][j-1] + dp[4][j-1]\n",
    "            dp[3][j] = dp[2][j-1] + dp[4][j-1]\n",
    "            dp[4][j] = dp[0][j-1]\n",
    "        return (dp[0][n] + dp[1][n] + dp[2][n] + dp[3][n] + dp[4][n]) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "\n",
    "        # Solution: Dynamic Programming\n",
    "\n",
    "        # Step 1: Construct the state-transition matrix\n",
    "        dp = [[0] * 5 for _ in range(n)]\n",
    "\n",
    "        # Step 2: Set the initial state\n",
    "        for i in range(5):\n",
    "            dp[-1][i] = 1\n",
    "        \n",
    "        # Step 3: Define the state-transition relationship\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            dp[i][0] = dp[i + 1][1]\n",
    "            dp[i][1] = dp[i + 1][0] + dp[i + 1][2]\n",
    "            dp[i][2] = dp[i + 1][0] + dp[i + 1][1] + dp[i + 1][3] + dp[i + 1][4]\n",
    "            dp[i][3] = dp[i + 1][2] + dp[i + 1][4]\n",
    "            dp[i][4] = dp[i + 1][0]\n",
    "        \n",
    "        return sum(dp[0]) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        # 根据约束条件 n >=1\n",
    "        # dp[i]['a'] 表示长度是 i 且结尾是 a 的字符串个数\n",
    "        # dp[1]['a'] 至少是 5，可以都初始化成 5？\n",
    "        a, e, i, o, u = 'aeiou'\n",
    "        dp = [{k:0 for k in 'aeiou'} for _ in range(n+1)]  # 第一个维度是 i ，第二个维度是 aeiou\n",
    "        print(dp)\n",
    "\n",
    "        for v in 'aeiou':\n",
    "            dp[1][v] = 1\n",
    "        \n",
    "        for j in range(2, n+1):\n",
    "            # a => i OR u\n",
    "            # - e => a OR i\n",
    "            # - i => e OR o\n",
    "            # - o => i\n",
    "            # - u => i OR o\n",
    "            dp[j][a] = dp[j-1][e]\n",
    "            dp[j][e] = dp[j-1][a] + dp[j-1][i]\n",
    "            dp[j][i] = dp[j-1][a] + dp[j-1][e] + dp[j-1][o] + dp[j-1][u]\n",
    "            dp[j][o] = dp[j-1][i] + dp[j-1][u]\n",
    "            dp[j][u] = dp[j-1][a]\n",
    "        \n",
    "\n",
    "        return sum(dp[n].values()) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        voweltoidx = {\"a\": 0, \"e\": 1, \"i\":2, \"o\":3, \"u\":4}\n",
    "        idxtovowel = [\"a\", \"e\", \"i\", \"o\", \"u\"]\n",
    "        M = 10^9 + 7\n",
    "        aftervowels = {\"a\": [\"e\", \"i\", \"u\"], \"e\": [\"a\", \"i\"], \"i\": [\"e\", \"o\"], \"o\": [\"i\"], \"u\": [\"i\", \"o\"]}\n",
    "        dp = [[0]*(n+1) for i in range(5)]\n",
    "        for i in range(5):\n",
    "            dp[i][1] = 1\n",
    "\n",
    "        for l in range(2, n+1):\n",
    "            for v in range(5):\n",
    "                for before in aftervowels[idxtovowel[v]]:\n",
    "                    beforeletteridx = voweltoidx[before]\n",
    "                    dp[v][l] += dp[beforeletteridx][l-1]\n",
    "            dp[v][l] %= 1000000007\n",
    "        return (dp[0][n] + dp[1][n] + dp[2][n] + dp[3][n] + dp[4][n]) % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        dp=[[0]*n for _ in range(5)]\n",
    "        for i in range(5):\n",
    "            dp[i][0]=1\n",
    "        for i in range(1,n):\n",
    "            dp[0][i]=dp[1][i-1]+dp[2][i-1]+dp[4][i-1]\n",
    "            dp[1][i]=dp[0][i-1]+dp[2][i-1]\n",
    "            dp[2][i]=dp[1][i-1]+dp[3][i-1]\n",
    "            dp[3][i]=dp[2][i-1]\n",
    "            dp[4][i]=dp[2][i-1]+dp[3][i-1]\n",
    "        ans=0\n",
    "        for i in range(5):\n",
    "            ans+=(dp[i][-1]%(10**9+7))\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        res = 0\n",
    "        table = {}\n",
    "        for c in 'aeiou':\n",
    "            res += self.search(n, c, table)\n",
    "        return res % int(1e9 + 7)\n",
    "\n",
    "    def search(self, n, c, table):\n",
    "        if (n, c) not in table:\n",
    "            if n == 1:\n",
    "                table[(n, c)] = 1\n",
    "            else:\n",
    "                if c == 'a':\n",
    "                    table[(n, c)] = self.search(n - 1, 'e', table)\n",
    "                elif c == 'e':\n",
    "                    table[(n, c)] = self.search(n - 1, 'a', table) + self.search(n - 1, 'i', table)\n",
    "                elif c == 'i':\n",
    "                    table[(n, c)] = self.search(n - 1, 'a', table) + self.search(n - 1, 'e', table) + self.search(n - 1, 'o', table) + self.search(n - 1, 'u', table)\n",
    "                elif c == 'o':\n",
    "                    table[(n, c)] = self.search(n - 1, 'i', table) + self.search(n - 1, 'u', table)\n",
    "                elif c == 'u':\n",
    "                    table[(n, c)] = self.search(n - 1, 'a', table)\n",
    "        return table[(n, c)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        f = {}\n",
    "        for x in ('a', 'e', 'i', 'o', 'u'):\n",
    "            f[x] = [0]*(n+1)\n",
    "            f[x][1] = 1\n",
    "        \n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            f['a'][i] = f['e'][i-1] + f['i'][i-1] + f['u'][i-1]\n",
    "            f['e'][i] = f['a'][i-1] + f['i'][i-1]\n",
    "            f['i'][i] = f['e'][i-1] + f['o'][i-1]\n",
    "            f['o'][i] = f['i'][i-1]\n",
    "            f['u'][i] = f['i'][i-1] + f['o'][i-1]\n",
    "        #print(f)\n",
    "        res = 0\n",
    "        for x in ('a', 'e', 'i', 'o', 'u'):\n",
    "            res += f[x][n]\n",
    "        return res%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        # 01234 对应 aeiou, dp[i][j] 为以j结尾的种类数\n",
    "        dp = [[1]*5 for i in range(n)]\n",
    "        for i in range(1,n): # 能跟的都可以加上\n",
    "            dp[i][0] = dp[i-1][1] + dp[i-1][2] + dp[i-1][4]\n",
    "            dp[i][1] = dp[i-1][0] + dp[i-1][2]\n",
    "            dp[i][2] = dp[i-1][1] + dp[i-1][3]\n",
    "            dp[i][3] = dp[i-1][2]\n",
    "            dp[i][4] = dp[i-1][2] + dp[i-1][3]\n",
    "        return sum(dp[-1]) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        dp = [[0 for _ in range(5)] for __ in range(n)]\n",
    "        for i in range(5):\n",
    "            dp[0][i] = 1\n",
    "\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] = dp[i-1][2] + dp[i-1][4] + dp[i-1][1]\n",
    "            dp[i][1] = dp[i-1][2] + dp[i-1][0]\n",
    "            dp[i][2] = dp[i-1][1] + dp[i-1][3]\n",
    "            dp[i][3] = dp[i-1][2]\n",
    "            dp[i][4] = dp[i-1][3] + dp[i-1][2]\n",
    "\n",
    "        return int(sum(dp[n-1])%(10**9+7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 5\n",
    "        dp = {}\n",
    "        dp[1] = {'a':1, 'e':1, 'i':1, 'o':1, 'u':1}\n",
    "        for i in range(2, n+1):\n",
    "            prev = dp[i-1]\n",
    "            newM = {}\n",
    "            newM['e'] = prev['a'] + prev['i']\n",
    "            newM['a'] = prev['i'] + prev['u'] + prev['e']\n",
    "            newM['i'] = prev['e'] + prev['o']\n",
    "            newM['o'] = prev['i']\n",
    "            newM['u'] = prev['o'] + prev['i']\n",
    "\n",
    "\n",
    "            dp[i] = newM\n",
    "\n",
    "        m1 =  dp[n]\n",
    "        return sum(m1.values()) %(10**9+7)\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.countVowelPermutation(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        dp = {}\n",
    "        vowel = ['a','e','i','o','u']\n",
    "        for i in vowel:\n",
    "            dp[1,i] = 1\n",
    "        \n",
    "        for k in range(2, n+1):\n",
    "            dp[k,'a'] = dp[k-1,'e'] + dp[k-1,'i'] + dp[k-1,'u']\n",
    "            dp[k,'e'] = dp[k-1,'a'] + dp[k-1,'i']\n",
    "            dp[k,'i'] = dp[k-1,'e'] + dp[k-1,'o']\n",
    "            dp[k,'o'] = dp[k-1,'i']\n",
    "            dp[k,'u'] = dp[k-1,'i'] + dp[k-1,'o']\n",
    "        \n",
    "        return sum([dp[n,i] for i in vowel]) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        trans_to = {\n",
    "            0: [1],\n",
    "            1: [0, 2],\n",
    "            2: [0, 1, 3, 4],\n",
    "            3: [2, 4],\n",
    "            4: [0]\n",
    "        }\n",
    "        trans_f = {\n",
    "            0: [1, 2, 4],\n",
    "            1: [0, 2],\n",
    "            2: [1, 3],\n",
    "            3: [2],\n",
    "            4: [2, 3]\n",
    "        }\n",
    "\n",
    "        dp = [[0 for i in range(n + 1)] for _ in range(5)]\n",
    "        for _ in range(5):\n",
    "            dp[_][1] = 1\n",
    "        for col in range(2, n + 1):\n",
    "            for r in range(5):\n",
    "                dp[r][col] = sum([dp[_][col - 1] for _ in trans_f[r]])\n",
    "\n",
    "        return sum(dp[_][n] for _ in range(5)) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        self.dy = {}\n",
    "        return (self.startwith_a(0, n) + \\\n",
    "               self.startwith_e(0, n) + \\\n",
    "               self.startwith_i(0, n) + \\\n",
    "               self.startwith_o(0, n) + \\\n",
    "               self.startwith_u(0, n)) % (10**9 + 7)\n",
    "\n",
    "    def check(func) -> int:\n",
    "        def wrapper(*args, **kargs):\n",
    "            sf, idx, n= args\n",
    "            if idx >= n:\n",
    "                return 0\n",
    "            if idx == n-1:\n",
    "                return 1\n",
    "            key = f'{func.__name__}-{idx}'\n",
    "            if key not in sf.dy:\n",
    "                value = func(sf, idx, n)\n",
    "                sf.dy[key] = value ##% (10**9 + 7)\n",
    "            return sf.dy[key]\n",
    "        return wrapper\n",
    "\n",
    "    @check\n",
    "    def startwith_a(self, idx: int, n: int) -> int:\n",
    "        if idx == n-2:\n",
    "            return 1\n",
    "        return self.startwith_a(idx+2, n)+self.startwith_i(idx+2, n)\n",
    "\n",
    "    @check\n",
    "    def startwith_e(self, idx: int, n: int) -> int:\n",
    "        if idx == n-2:\n",
    "            return 2\n",
    "        return self.startwith_a(idx+1, n)+ self.startwith_i(idx+1, n)\n",
    "\n",
    "    @check\n",
    "    def startwith_i(self, idx: int, n: int) -> int:\n",
    "        return self.startwith_a(idx+1, n)+\\\n",
    "        self.startwith_e(idx+1, n)+\\\n",
    "        self.startwith_o(idx+1, n)+\\\n",
    "        self.startwith_u(idx+1, n)\n",
    "    \n",
    "    @check\n",
    "    def startwith_o(self, idx: int, n: int) -> int:\n",
    "        return self.startwith_i(idx+1, n)+self.startwith_u(idx+1, n)\n",
    "\n",
    "    @check\n",
    "    def startwith_u(self, idx: int, n: int) -> int:\n",
    "        return self.startwith_a(idx+1, n)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelPermutation(self, n: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        letters = {'a':['e','i','u'], 'e':['a', 'i'], 'i':['e', 'o'], 'o':['i'], 'u':['i', 'o']}\n",
    "        map = {'a':0, 'e':1,'i':2,'o':3,'u':4}\n",
    "        dp = [[0] * 5 for _ in range(n)]\n",
    "        for j in range(5):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(1, n):\n",
    "            for letter, values in letters.items():\n",
    "                j = map[letter]\n",
    "                for value in values:\n",
    "                    temp = map[value]\n",
    "                    dp[i][j] += dp[i - 1][temp]\n",
    "\n",
    "        return sum(dp[-1]) % MOD"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
